
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {

    /**
     * 第一遍
     * @param head
     * @return
     */
//    public ListNode detectCycle(ListNode head) {
//        // slow走一步，fast走两步
//        ListNode slow = head;
//        ListNode fast = head;
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if (fast == slow) break;
//        }
//
//        // 没有环
//        if (fast == null || fast.next == null) return null;
//
//        // 重新指向头节点,因为在两者相遇之后再走k-m步即可到达环起点，
//        // 这里将slow，fast设置为都走一步，
//        slow = head;
//        while (slow != fast) {
//            fast = fast.next;
//            slow = slow.next;
//        }
//        return slow;
//    }


    /**
     * 第二遍
     * @param head
     * @return
     */
//    public ListNode detectCycle(ListNode head) {
//        // slow走一步，fast走两步
//        ListNode slow = head;
//        ListNode fast = head;
//
//        // 有环
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if (fast == slow) break;
//        }
//
//        // 没有环
//        if (fast == null || fast.next == null) return null;
//
//        // 【记住：slow走一步，fast走两步，当两者第一次相遇之后将slow放回远点，
//        //  让两者同步频，则他们会在环起点相遇】
//        slow = head;
//        while (slow != fast) {
//            slow = slow.next;
//            fast = fast.next;
//        }
//        return slow;
//    }


    /**
     * 第三遍
     * @param head
     * @return
     */
//    public ListNode detectCycle(ListNode head) {
//        ListNode slow = head, fast = head;
//
//        // 有环
//        while (fast != null && fast.next != null) {
//            // 让slow走一步，fast走两步
//            fast = fast.next.next;
//            slow = slow.next;
//
//            if (slow == fast) break;
//        }
//
           // 没有环
//        if (fast == null || fast.next == null) return null;
//        slow = head;
//        while (slow != fast) {
//            slow = slow.next;
//            fast = fast.next;
//        }
//        return slow;
//    }


    /**
     * 第四遍
     * @param head
     * @return
     */
//    public ListNode detectCycle(ListNode head) {
//        ListNode slow = head, fast = head;
//
//        // 有环
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if (slow == fast) break;
//        }
//
//        // 没有环【注意这个语句一定要放下这里】
//        if (fast == null || fast.next == null) return null;
//
//        slow = head;
//        while (slow != fast) {
//            slow = slow.next;
//            fast = fast.next;
//        }
//        return slow;
//    }


    /**
     * 第五遍 2/27
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;

        // 有环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) break;
        }

        // 没有环
        if (fast == null || fast.next == null) return null;

        slow = head;
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
